package com.duoduo.剑指Offer;

import java.util.HashMap;
import java.util.Map;

/**
 * @program: algorithm
 * @description: 青蛙跳台阶问题15
 * 一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
 *
 * 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
 *
 * 示例 1：
 *
 * 输入：n = 2
 * 输出：2
 *
 * @author: chaidl  ！
 * @create: 2022-05-24 00:31
 */
public class 青蛙跳台阶问题15 {
	public static void main(String[] args) {
		numWays(5);
	}
	public static int numWays(int n) {
		if(n==0){
			return 1;
		}
		if (n==1){
			return 1;
		}
		if (n==2){
			return 2;
		}
		int a=1,b=2;
		int result=0;
		for (int i = 3; i <= n; i++) {
			result=(a+b)%1000000007;
			a=b;
			b=result;
		}
		return result;
	}
	static Map<Integer,Integer> map = new HashMap<Integer, Integer>();
	public static int numWays2(int n) {
		if (n==0 || n==1){
			return 1;
		}
		if (n == 2) {
		    return 2;
		}
		if (null!=map.get(n)){
			return map.get(n);
		}else {
			int tmp = (numWays2(n - 1) + numWays2(n - 2)) % 1000000007;
			map.put(n, tmp);
			return tmp;
		}
	}
}
